package com.nav.util;

import java.util.ArrayList;
import java.util.List;

public class Primes {
	public static List<Integer> getPrimesBelow(int n) {
		boolean isComp[] = new boolean[n];
		isComp[0] = isComp[1] = true;
		List<Integer> l = new ArrayList<Integer>();
		for(int i = 2; i < n; i++) {
			if(isComp[i])
				continue;
			l.add(i);
			for(int j = 2 * i; j < n; j += i)
				isComp[j] = true;
		}
		return l;
	}
	public static boolean isPrime(int n) {
		int l = (int)java.lang.Math.sqrt(n);
		for(int i = 2; i <= l; i++)
			if(n % i == 0)
				return false;
		return true;
	}
	public static void main(String[] args) {
		System.out.println(isPrime(37));
		List<Integer> l = getPrimesBelow(100000);
		System.out.println(l.size() + ": " + l);
	}
}
